package main

import "fmt"

/*
二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
1.双指针记录头结点和前驱

2.中序遍历顺着Left指针入栈，为了不破坏次序。利用Right指针在回溯的过程中指向上一层的节点（强行解释）。
但已经回溯到上一层时怎么利用之前的节点呢。那就用pre变量保存前驱节点。当前节点（实际上已经回溯到上一层了）
的Left指针指向前驱。这样约定好了之后。递归处理即可

3.置为双向循环链表

*/

func Convert(root *TreeNode) *TreeNode {
	// write code here
	if root == nil {
		return nil
	}
	var st []*TreeNode
	var pre, head *TreeNode
	for len(st) > 0 || root != nil {
		for root != nil {
			st = append(st, root)
			root = root.Left
		}
		cur := st[len(st)-1]
		st = st[:len(st)-1]
		if pre != nil {
			pre.Right = cur
		} else {
			head = cur
		}
		cur.Left = pre
		pre = cur
		root = cur.Right
	}
	// niu客不要求循环链表
	//     head.Left = pre
	//     pre.Right = head
	return head
}

func main() {
	A := &TreeNode{Val: 1}
	A.Left = &TreeNode{Val: 2}
	A.Right = &TreeNode{Val: 3}
	A.Left.Left = &TreeNode{Val: 4}
	A.Left.Right = &TreeNode{Val: 5}
	A.Right.Left = &TreeNode{Val: 6}
	fmt.Println(Convert(A))
}
